Теорема о формуле чисел Каталана

$$C_n = \frac{1}{n+1} \binom{2n}{n}$$

!lower_path.svg Поскольку общее количество путей в $(n, n)$-решетке равно $\binom{2n}{n}$, вместо верхних путей будем подсчитывать все остальные (назовем их **неверхними**). Добавим к $(n, n)$-решетке один ряд снизу и проведем **нижнюю диагональ** $y = x - 1$: - Рассмотрим $(n-1, n+1)$-решетку с углами $(1, -1)$ и $(n, n)$. - Любой путь $P$ из $(1, -1)$ в $(n, n)$ начинается ниже нижней диагонали, а заканчивается выше нее. - $\implies P$ пересекает эту диагональ; рассмотрим первую (нижнюю) точку касания $K$. - Фрагмент $P$ ниже $K$ отразим относительно нижней диагонали. - Остальная часть $P$ не изменяется. - Получим путь $P'$ из $(0, 0)$ в $(n, n)$. - $P'$ — неверхний, потому что проходит через точку $K$. Положив $f(P) = P'$ для всех $P$, получили функцию из множества путей в $(n-1, n+1)$-решетке во множество неверхних путей в $(n, n)$-решетке. - $f$ — **инъекция**: - Пути $P_1$ и $P_2$ отличаются фрагментом до точки $K$ или фрагментом после нее. - $\implies f(P_1)$ и $f(P_2)$ тоже отличаются этим фрагментом. - $f$ — **сюрьекция**: - Для неверхнего пути $P'$ возьмем самую левую точку $K$ на диагонали $y = x - 1$. - Отразим фрагмент $P'$ до точки $K$ относительно этой диагонали. - $\implies$ Полученный путь $P$ будет прообразом $P'$ относительно $f$. $\implies f$ — **биекция**. $\implies$ Число неверхних путей в $(n, n)$-решетке равно числу путей в $(n-1, n+1)$-решетке. $\implies$ Число верхних путей в $(n, n)$-решетке есть: $$\begin{align} C_n &= \binom{2n}{n} - \binom{2n}{n-1} = \frac{(2n)!}{n!n!} - \frac{(2n)!}{(n-1)!(n+1)!} = \frac{(n+1)(2n)! - n(2n)!}{n!(n+1)!} \\ &= \frac{(2n)!}{n!(n+1)!} = \frac{1}{n+1} \frac{(2n)!}{n!n!} = \frac{1}{n+1} \binom{2n}{n} \end{align}$$ $\square$